package code801_900.code40_50;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。
 *
 * 给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；
 * 否则，返回 false 。
 *
 * 输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
 * 输出：true
 * 解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。
 *
 * 输入：hand = [1,2,3,4,5], groupSize = 4
 * 输出：false
 * 解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。
 */
public class _846isNStraightHand {

    /**
     * 最简单方法：快速排序选择连续即可
     * 另一种思路：从头开始遍历，如果顺序增加则不管，如果出现曾经出现的小正数，则另起一个序列
     *
     * 题解中给出方法是：贪心
     * 执行用时：     * 25 ms     * , 在所有 Java 提交中击败了     * 83.64%     * 的用户
     * 内存消耗：     * 39.8 MB     * , 在所有 Java 提交中击败了     * 36.36%     * 的用户
     *
     * @param hand
     * @param groupSize
     * @return
     */
    public boolean isNStraightHand(int[] hand, int groupSize) {
        if(hand.length%groupSize!=0)return false;
        Arrays.sort(hand);
        Map<Integer,Integer> cnt = new HashMap<>();
        for(int x : hand){
            cnt.put(x,cnt.getOrDefault(x,0)+1);
        }
        for(int x : hand){
            if(!cnt.containsKey((x)))continue;
            for (int i = 0; i < groupSize; i++) {
                int num = x + i;
                if(!cnt.containsKey(num))return false;
                cnt.put(num,cnt.get(num)-1);
                if(cnt.get(num)==0)cnt.remove(num);
            }
        }
        return true;
    }

}
